public class Sort {
    public void mergerSort(int[] array){
        mergerFunc(array,0, array.length-1);
    }
    public void mergerFunc1(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int mid = (left+right)/2;
        //分解左边
        mergerFunc(array,left,mid);
        //分解右边
        mergerFunc(array,mid+1,right);
        //合并
        merger(array,left,right,mid);
    }
    public void mergerFunc(int[] array,int left,int right){
        int gap = 1;
        while ((gap< array.length)){
            for(int i = 0;i< array.length;i+=gap*2){
                int s1 = i;
                int e1 = s1+gap-1;
                if(e1>= array.length){
                    e1 = array.length-1;
                }
                int s2 = e1+1;
                if(s2>= array.length){
                    s2 = array.length-1;
                }
                int e2 = s2+gap-1;
                if(e2>= array.length){
                    e2 = array.length-1;
                }
                merger(array,s1,e2,e1);
            }
            gap*=2;
        }
    }
    public void merger(int[] array,int start,int end,int midIndex){
        int[] tmpArr = new int[end-start+1];
        int k = 0;
        int s1 = start;
        int s2 = midIndex+1;

        while(s1<=midIndex&&s2<=end){
            if(array[s1]<=array[s2]){
                tmpArr[k++] = array[s1++];
            }else {
                tmpArr[k++] = array[s2++];
            }
        }
        while(s1<=midIndex){
            tmpArr[k++] = array[s1++];
        }
        while (s2<=end){
            tmpArr[k++] = array[s2++];
        }
        for(int i = 0;i<k;i++){
            array[start+i] = tmpArr[i];
        }
    }
}
